

#define maxn  16000

int a[maxn],c[maxn],b[maxn];
int mid;
/*************2-sat模板*********************/
template<int maxv,int maxe>
struct SAT
{
    int first[maxv],next[maxe],E[maxe],M;
        int N ;   //N为点数， 总共的点，也就是乘以2后的点
    int dfn[maxv],low[maxv],sta[maxv],belong[maxv],bcnt,dindex,top,instack[maxv],op[maxv];  //缩点是0到bcnt-1
        void initop(int len)//构造正反对，并确定怎么标号
        {
           N=len;
           for(int i=0; i<len; i+=2)//0到n-1的范围
            {
                op[i]=i+1;
                op[i+1]=i;
            }
        }
        void init()//初始化边
        {
            M=-1;
            memset(first,-1,sizeof(first));
        }
        void insert(int a,int b)
        {
            M++;
            next[M]=first[a];
            first[a]=M;
            E[M]=b;
        }
        void   build()//建边这个地方可能需要随时修改
        {
            int i;
           
            int x,y,p,q;
            for(i=0; i<=mid; i++)
            {
                   x=a[i]*2;
                p=op[x];
                y=b[i]*2;
                q=op[y];
                if(c[i]==0)
                {
                    insert(op[x],y);
                    insert(op[y],x);
                }
                else if(c[i]==1)
                {
                     insert(x,y);
                    insert(y,x);
                    
                    insert(op[x],op[y]);
                    insert(op[y],op[x]);
                }
                else if(c[i]==2)
                {
                    insert(x,op[y]);
                    insert(y,op[x]);
                }
            }
           
        }

        void tarjan(int u)
        {
            int e,v;
            dfn[u]=low[u]=++dindex;
            instack[u]=1;
            sta[++top]=u;
            for(e=first[u]; e!=-1; e=next[e])
            {
                v=E[e];
                if(!dfn[v])
                {
                    tarjan(v);
                    if(low[v]<low[u])
                        low[u]=low[v];
                }
                else if(instack[v]&& dfn[v]<low[u])
                    low[u]=dfn[v];
            }
            if(dfn[u]==low[u])
            {
                do{
                    v=sta[top--];
                    instack[v]=0;
                    belong[v]=bcnt;
                }while(v!=u);
                  bcnt++;
            }
        }
        bool   judge()
        {
            for(int i=0; i<N; i++)
                if(belong[i]==belong[op[i]])
                    return false;
            return true;
        }
        int   solve()
        {
            int i;
            memset(dfn,0,sizeof(dfn));
            top=bcnt=dindex=0;
            for( i=0; i<N; i++)
                if(!dfn[i])
                    tarjan(i);
            if(judge())
            {
                return 1;
            }
            else return 0;
        }
};
SAT<1100,160000> sat;//第一个是点，第二个是边
/*************2-sat模板*********************/
int main()
{
int n,m;
     #ifndef ONLINE_JUDGE
        freopen("in","r",stdin);
    #endif
    int t,i,j,k;
    int ans,l=0,r=m-1;
     scanf("%d", &t);
    while(t--)
    {
        
        scanf("%d%d", &n, &m);
        /*************2-sat模板*********************/
        sat.initop(n*2); //传入总共的点，也就是乘以2后的点
        /*************2-sat模板*********************/
        for(i=0; i<m; i++)
        {
            scanf("%d%d%d", &a[i],&b[i], &c[i]);
        }    
         l=0;r=m-1;
         ans=-1;
        while(l<=r)
        {
            mid=(l+r)/2;
            /*************2-sat模板*********************/
            sat.init();//注意标号乘以了2倍
            sat.build();//注意标号乘以了2倍
            /*************2-sat模板*********************/
            if(sat.solve())
           /*************2-sat模板*********************/ 
               {
                ans=mid;
                l=mid+1;
            }
            else r=mid-1;
        }
        printf("%d\n",ans+1);
    }
    
}

